#include<iostream>
#include<vector>
using std::endl;
using std::cout;
using std::vector;
#define SIZE(a) (sizeof(a)/sizeof(a[0]))
#define N 10  


//i 是基准 父节点index //size 数组长度
void heap_init(int *arr,int i,int size){
    //从后往前，找最后一个父节点 跟子节点进行比较
    int dad_idx = i;
    int son_idx = i*2 + 1;
    while(son_idx < size){
        //子节点进行比较
        //if(son_idx+1 < size && arr[son_idx] < arr[++son_idx]);
        if(son_idx+1 < size && arr[son_idx] < arr[son_idx + 1]) {
            ++son_idx;
        }
 
        //与父节点比较
        //son_idx + 1 NO 不然走不了
        if(arr[son_idx] > arr[dad_idx]){
            std::swap(arr[son_idx],arr[dad_idx]);
            //父子节点变一下
            dad_idx = son_idx;
            son_idx = dad_idx*2+1;
        }else{
            break;
        }
    }
}

//heap_sort
void heap_sort(int *arr){
    //构建大根堆
    for(int i = N/2 - 1;i>=0;--i){
        heap_init(arr,i,N);
    }
     
    //排序
    //先拿一遍
    std::swap(arr[0],arr[N-1]);
    for(int size = N-1;size > 1;--size){
        //重新大根堆
        heap_init(arr,0,size);
        //拿最后一个 这里也要减
        std::swap(arr[0],arr[size-1]);
    }
}

int test0(){
    int arr[] = {32,13,45,89,12,1,8,17};
    cout << "sizeof(arr): " << sizeof(arr) << endl;
    heap_sort(arr);
    for(auto &ele : arr){
        cout<<ele<<" ";
    }
    cout<<endl;
}
void test() {
    srand(time(NULL));
    int *arr = (int *)malloc(sizeof(int) * 10);
    for(int i = 0; i <  10; i++ ) {
        arr[i] = rand() % 100;
    }
    for(int i = 0;i<10;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    heap_sort(arr);
    for(int i = 0;i<N;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
int main(void){
    test();
}
